/**
 *  @file HeapSort.cpp
 */

#include "SortAlgorithm.h"

namespace cppflib
{

namespace collections
{

namespace sort
{

/*
 *  Heap starts at 1, but in C array starts at 0.
 *  These 2 functions are to locate the zero-based array index.
 */
PRIVATE int __LeftChild(int i)
{ 
   return (((i + 1) * 2) - 1);
}

PRIVATE int __RightChild(int i)
{
   return ((i + 1) * 2);
}

/**
 *  To "bubble" up value in a heap according to the compare function
 *  "cmpFunc". This will call itself recursively down to the leaf node.
 *
 *  @param [in] startPos -- zero based starting node
 *  @param [in] offset -- offset from the original collection
 *  @param [in] heapSize -- size of the heap (to ensure retrieving elements will be within the collection itself)
 */
PRIVATE void __Heapify(ICollection &collection, const int startPos, const int offset, const int heapSize, const SortCmpFunc &cmpFunc)
{
    int left = __LeftChild(startPos) + offset;
    int right = __RightChild(startPos) + offset;
    int curPos = startPos + offset; 
    int index = curPos;
    
    /*
     *  find the largest index: parent, left child or right child
     */
    if (left < heapSize && cmpFunc(collection.Element(left), collection.Element(curPos)) > 0)
       index = left;
    
    if (right < heapSize && cmpFunc(collection.Element(right), collection.Element(index)) > 0)
       index = right;

    if (index != curPos) {
      // swap value
      collection.Swap(curPos, index);
      // call itself recursively
      __Heapify(collection, index - offset, offset, heapSize, cmpFunc);
    }

}

/**
 *   To build the heap by calling "__Heapify()" repeatedly.
 *
 *   @param [in] startIndex -- starting index to be sorted
 *   @param [in] count -- number of elements to be sorted
 */
PRIVATE void __BuildHeap(ICollection &collection, const int startIndex, const int count, const SortCmpFunc &cmpFunc)
{
    
    for (int i = (count / 2 - 1); i >= 0; --i) {
       __Heapify(collection, i, startIndex, (startIndex + count), cmpFunc);
    }

}

/**
 *  The sorting algorithm is quite simple:
 *     1) call "BuildHeap" first to build a heap
 *     2) the max/min value will then be at the root
 *     3) swap the root element with end of the array
 *     4) decrement the heap size by 1 and call "Heapify"
 *        to make sure the next max/min value will be
 *        at root again.
 *
 *  @param [in,out] collection -- data collection set. The collection will be sorted upon returning. 
 *  @param [in] startIndex -- zero based start index
 *  @param [in] count -- number of elements which involved in sorting
 *  @param [in] cmpFunc -- comparison function
 */
_DLLAPI void HeapSort(ICollection &collection, const int startIndex, const int count, const SortCmpFunc &cmpFunc)
{
    // Build heap first
    __BuildHeap(collection, startIndex, count, cmpFunc);

    int heapSize = startIndex + count;
    
    for (int i = heapSize - 1; i >= startIndex + 1; --i) {
        //  exchange start and end element
        collection.Swap(startIndex, i);
        
        // decrement heap size by 1
        --heapSize;

        // call heapify so that the max/min value will be at root
        __Heapify(collection, 0, startIndex, heapSize, cmpFunc);
    }
}

}  // end of namespace sort

}  // end of namespace collections

}  // end of namespace cppflib

